package com.wfm.niuke.huisu;

import com.wfm.common.TreeNode;
import java.util.ArrayList;
import java.util.List;
import org.junit.Test;

/**
 * 需要以每个节点为起点进行dfs
 */
public class JZ84二叉树中和为某一值的路径3 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findPath (TreeNode root, int sum) {
        // write code here
        if(root==null) return res;
        dfs(root,sum);
        findPath(root.left,sum);
        findPath(root.right,sum);
        return res;
    }
    public void dfs(TreeNode root,int sum){
        if(root==null) return;
        path.add(root.val);
        if(root.val==sum){
            res.add(new ArrayList<>(path));
        }
        dfs(root.left,sum-root.val);
        dfs(root.right,sum-root.val);
        path.remove(path.size()-1);
    }

    @Test
    public void test(){
        TreeNode treeNode = TreeNode.generatorTreeNode("1,2,3,4,5,4,3,-2,null,-1,null,null,null,null,null,2");
        System.out.println(findPath(treeNode, 6));
    }
    @Test
    public void test2(){
        TreeNode treeNode = TreeNode.generatorTreeNode("1000000000,1000000000,null,294967296,null,1000000000,null,1000000000,null,1000000000");
        System.out.println(findPath(treeNode, 0));

    }
}
